/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>        // std::max()
#include <string>           // std::string
#include <vector>           // std::vector
#include <iostream>

using namespace std;

// 在未优化的动态规划版本中，每次仅在相邻的两行之间进行对比得出最大值。
// 故而我们可以继续优化以降低空间复杂度。
size_t max_common_substring(const string& s1, const string& s2)
{
    size_t m = s1.length();
    size_t n = s2.length();

    // 这个一维矢量用来保存前一行的结果。
    vector<size_t> prev(n + 1, 0);

    size_t ans = 0;
    for (size_t i = 1; i <= m; i++) {

        // 这个一维矢量用来保存当前行的结果。
        vector<size_t> curr(n + 1, 0);

        for (size_t j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                curr[j] = prev[j - 1] + 1;
                ans = max(ans, curr[j]);
            }
            else {
                curr[j] = 0;
            }
        }

        // 将矢量 curr 中的数据复制到 prev 中
        prev = curr;
    }

    return ans;
}

int main()
{
    string s1 = "One example";
    string s2 = "Two examples";
    cout << max_common_substring(s1, s2) << endl;
    return 0;
}

